/*
 * graph.h
 *
 *  Created on: Feb 17, 2011
 *      Author: correa
 */

#ifndef GRAPH_H_
#define GRAPH_H_

#include <stdio.h>

#define GSTERR_NEGATIVE_SURPLUS 						1

#define GSHERR_GRAPH_HAS_BEEN_LOADED_ALREADY 				1
#define GSHERR_ANTINEIGHBORHOOD_HAS_BEEN_SET_ALREADY		2
#define GSHERR_ANTINEIGHBORHOOD_SIZE_HAS_BEEN_SET_ALREADY	3
#define GSHERR_NEIGHBORHOOD_HAS_BEEN_SET_ALREADY			4
#define GSHERR_NEIGHBORHOOD_SIZE_HAS_BEEN_SET_ALREADY		5
#define GSHERR_VERTICES_IN_ORDER_ALREADY					6
#define GSHERR_CODE_NOT_VALID								7

// Graph

typedef struct AM {
	char * 		g;
	long		matrixsize;
	int			logrowsize;
	// number of vertices
	int	*		nverts;
	// number of edges
	long long *	nedges;
} adjMatrix;

typedef enum GT { GT_GRAPH, GT_COMPLEMENT } graphType;

inline static int inline_ceillog2(int n) {
	int c = 0;
	int l = 0;
	while (n > 1) {
		c |= (n & 1);
		n >>= 1;
		l++;
	}
	l += c;
	return l;
}

static char * 		_GRAPH_H_g;
static long 		_GRAPH_H_matrixsize;
static int 			_GRAPH_H_logrowsize;
// number of vertices
static int * 		_GRAPH_H_nverts;
// number of edges
static long long * 	_GRAPH_H_nedges;

#define newAdjMatrixSize(n) (_GRAPH_H_matrixsize = ((long) 1 << (_GRAPH_H_logrowsize = inline_ceillog2(n)-3))*(n))
#define newAdjMatrix(n) 	_GRAPH_H_g = (char *) malloc(newAdjMatrixSize((n))); \
							_GRAPH_H_nverts = (int *) malloc(sizeof(int)); \
							*_GRAPH_H_nverts = n; \
							_GRAPH_H_nedges = (long long *) malloc(sizeof(long long)); \
							*_GRAPH_H_nedges = 0

#define getAdjMatrix(a) (a)->g = _GRAPH_H_g; \
						(a)->matrixsize = _GRAPH_H_matrixsize; \
						(a)->logrowsize = _GRAPH_H_logrowsize; \
						(a)->nverts = _GRAPH_H_nverts; \
						(a)->nedges = _GRAPH_H_nedges
#define setAdjMatrix(a) _GRAPH_H_g = (a)->g; \
						_GRAPH_H_matrixsize = (a)->matrixsize; \
						_GRAPH_H_logrowsize = (a)->logrowsize; \
						_GRAPH_H_nverts = (a)->nverts; \
						_GRAPH_H_nedges = (a)->nedges
#define cloneAdjMatrix(dest, orig) (dest)->g = (char *) malloc((orig)->matrixsize); \
								   memcpy((dest)->g, (orig)->g, (orig)->matrixsize); \
								   (dest)->matrixsize = (orig)->matrixsize; \
								   (dest)->logrowsize = (orig)->logrowsize; \
								   (dest)->nverts = (int *) malloc(sizeof(int)); \
								   *((dest)->nverts) = *((orig)->nverts); \
								   (dest)->nedges = (int *) malloc(sizeof(int)); \
								   *((dest)->nedges) = *((orig)->nedges)
#define freeAdjMatrix() free(_GRAPH_H_g); \
						free(_GRAPH_H_nverts); \
						free(_GRAPH_H_nedges)
#define nverts()		(*_GRAPH_H_nverts)
#define nedges()		(*_GRAPH_H_nedges)
#define hasGraph() 		(_GRAPH_H_g != NULL)
#define edgeIndex(i, j) (((long) i << _GRAPH_H_logrowsize)+(j >> 3))
#define edgeMask(j) 	(1 << (char) (j & 0x07))
#define hasEdge(i, j) 	(_GRAPH_H_g[edgeIndex(i, j)] & edgeMask(j))
#define addEdge(i, j) 	(*_GRAPH_H_nedges)+=!hasEdge(i, j); \
						(_GRAPH_H_g[edgeIndex(i, j)] |= edgeMask(j))
#define delEdge(i, j) 	(*_GRAPH_H_nedges)-=(hasEdge(i, j)!=0); \
						(_GRAPH_H_g[edgeIndex(i, j)] &= ~edgeMask(j))
#define addAllEdges() 	(memset(_GRAPH_H_g, 0xFF, _GRAPH_H_matrixsize)); \
						(*_GRAPH_H_nedges) = nverts()*nverts()
#define delAllEdges() 	(memset(_GRAPH_H_g, 0, _GRAPH_H_matrixsize)); \
						(*_GRAPH_H_nedges) = 0

// additional structures (implemented in graphstrct.c)

int setDefaultGraph(adjMatrix * g);

int antiNeig(const adjMatrix * g, int r, const int * R, int i, int asz, int * ang, int * surplus_p);
int antiNeigs(const adjMatrix * g, int r, const int * R, int asz, int * ad, int * ang, int * surplus_p);
int antiNeigSize(adjMatrix * g, int r, int * R, int i, int * deg);
int antiNeigSizes(adjMatrix * g, int r, int * R, int * deg);

int neig(adjMatrix * g, int r, int * R, int i, int asz, int * ng, int * surplus_p);
int neigs(adjMatrix * g, int r, int * R, int asz, int * ad, int * ang, int * surplus_p);
int neigSize(adjMatrix * g, int r, int * R, int i, int * deg);
int neigSizes(adjMatrix * g, int r, int * R, int * deg);

// getters and setters in graphshare

int 				loadSharedGraph(FILE * graphFile, const graphType t);
const adjMatrix * 	getSharedGraph();
int 				setSharedGraph(const adjMatrix * adj);
int 				releaseSharedGraph(int code);
const int * 		getSharedOrder();
int 				setSharedOrder(int * const o, const int r, int code);
int			 		getSharedOrderSize();
const int * 		getAntiNeig(int i);
const int 			getAntiNeigSize(int i);
int 				setAntiNeig(int * const a, int i, int sz);
int 				releaseAntiNeig(int code);
const int *  		getNeig(int i);
const int 			getNeigSize(int i);
int 				setNeig(int * const a, int i, int sz);
int 				releaseNeig(int code);

// algorithms (implemented in graphalg.c)

int mcrSort(const adjMatrix * g, const int r, const int * d, const int ** ng, int * rank);
int mcrDegreeSort(const adjMatrix * g, const int r, const int * R, int * rank);
int mcrAntiDegreeSort(const adjMatrix * g, const int r, const int * R, int * rank);
int greedySort(const adjMatrix * g, const int r, const int * d, const int ** ng, const int k, int * cover);
int greedyColoringSort(const adjMatrix * g, const int r, const int * R, const int k, int * cover);
int greedyCliqueCoverSort(const adjMatrix * g, const int r, const int * R, const int k, int * cover);
int dsaturSort(const adjMatrix * g, const int r, const int * d, const int ** ng, const int k, int * cover);
int dsaturCliqueCoverSort(const adjMatrix * g, const int r, const int * R, const int k, int * cover);
int dsaturColoringSort(const adjMatrix * g, const int r, const int * R, const int k, int * cover);


#endif /* GRAPH_H_ */
